#include <stdio.h>
#include <stdlib.h>

//自定义bool类型
typedef enum bool {
    False = 0,
    True = 1
} bool;

typedef struct Link {
    int elem;
    struct Link *next;
} link;

link *init_table() {
    link *head = (link *) malloc(sizeof(link));
    head->elem = 1;
    head->next = NULL;
    link *temp = head;
    for (int i = 2; i < 6; i++) {
        link *new_node = (link *) malloc(sizeof(link));
        new_node->elem = i;
        new_node->next = NULL;
        temp->next = new_node;
        temp = new_node;
    }

    //把链表的两端连接起来
    temp->next = head;

    return head;
}

void display_table(link *head) {
    link *temp = head;
    while (head->next && head->next != temp) {
        printf("%d ", head->elem);
        head = head->next;
    }
    printf("%d \n", head->elem);
}

bool haveRing(link *head) {
    //遍历链表,每次都和自己的直接前驱对比是否有相同的节点,如果有,那么就有环
    long long address_arr[20] = {0};
    int len = 0;

    link *temp = head;
    while (temp->next) {

        for (int i = 0; i < len; ++i) {
            if (address_arr[i] == temp) {
                return True;
            }
        }

        address_arr[len] = temp;
        len++;
        temp = temp->next;
    }

    return False;
}

bool haveRingTwo(link *head) {
    link *h1 = head->next;
    link *h2 = head;
    while (h1) {
        if (h1 == h2) {
            return True;
        } else {
            h1 = h1->next;
            if (!h1) {
                return False;
            } else {
                h1 = h1->next;
                h2 - h2->next;
            }

        }
    }
    return False;

}

int main() {
    link *head = init_table();
    display_table(head);
    bool ring = haveRing(head);
    printf("链表是否有环: %d \n", ring);
    bool ring_two = haveRingTwo(head);
    printf("链表是否有环: %d \n", ring_two);
    return 0;
}